package Queue_and_Stack;

/*
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/queue-stack/g9d0h/
 */

import java.util.*;

public class _32有效的括号 {
    public static void main(String[] args) {

        String s;
        s = "({}){}";
        System.out.println(isValid2(s));


    }

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Stack<Character> tempstack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            stack.push(c);
        }

        for (int i = 0; i < s.length(); i++) {
            boolean flag = false;
            Character pop = stack.pop();
            if(tempstack.isEmpty()){
                tempstack.push(pop);
                continue;
            }
            Character peek = tempstack.peek();
            switch (peek) {
                case '(':
                    peek = ')';
                    break;
                case ')':
                    peek = '(';
                    flag = true;
                    break;
                case '[':
                    peek = ']';
                    break;
                case ']':
                    peek = '[';
                    flag = true;
                    break;
                case '{':
                    peek = '}';
                    break;
                case '}':
                    peek = '{';
                    flag = true;
                    break;
            }
            if(!flag){
                return false;
            }
            if(pop.equals(peek)){
                tempstack.pop();
            }else {
                tempstack.push(pop);
            }
        }
        return tempstack.isEmpty();
    }

    //官解
//    class Solution {
        public static boolean isValid2(String s) {
            int n = s.length();
            if (n % 2 == 1) {
                return false;
            }

            Map<Character, Character> pairs = new HashMap<Character, Character>() {{
                put(')', '(');
                put(']', '[');
                put('}', '{');
            }};
            Deque<Character> stack = new LinkedList<Character>();
            for (int i = 0; i < n; i++) {
                char ch = s.charAt(i);
                if (pairs.containsKey(ch)) {
                    if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                        return false;
                    }
                    stack.pop();
                } else {
                    stack.push(ch);
                }
            }
            return stack.isEmpty();
        }
//    }


}
